package com.fan.floyd;

import java.util.Arrays;

/**
 * 弗洛伊德算法，最短路径
 * @author 19252
 * @date 2020/8/9
 */
public class FloydDemo {

    public static void main(String[] args) {
        char[] vertexArray = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        FloydGraph graph = new FloydGraph(vertexArray.length, vertexArray);
        // 为图添加边
        graph.setEdge(0, 1, 5);
        graph.setEdge(0, 2, 7);
        graph.setEdge(0, 6, 2);
        graph.setEdge(1, 0, 5);
        graph.setEdge(1, 3, 9);
        graph.setEdge(1, 6, 3);
        graph.setEdge(2, 0, 7);
        graph.setEdge(2, 4, 8);
        graph.setEdge(3, 1, 9);
        graph.setEdge(3, 5, 4);
        graph.setEdge(4, 2, 8);
        graph.setEdge(4, 5, 5);
        graph.setEdge(4, 6, 4);
        graph.setEdge(5, 3, 4);
        graph.setEdge(5, 4, 5);
        graph.setEdge(5, 6, 6);
        graph.setEdge(6, 0, 2);
        graph.setEdge(6, 1, 3);
        graph.setEdge(6, 4, 4);
        graph.setEdge(6, 5, 6);
        graph.showGraph();
        System.out.println();
        graph.showVertexMatrix();
    }
}

class FloydResult{

    
    public static void floyd(FloydGraph graph){
        int length = 0;
        // 中间顶点
        for (int i = 0; i < graph.getVertexNum(); i++) {
            // 出发顶点
            for (int j = 0; j < graph.getVertexNum(); j++) {
                // 终点
                for (int k = 0; k < graph.getVertexNum(); k++) {
                    length = graph.getMatrix()[j][i] + graph.getMatrix()[i][k];
                    // 这里的意思和迪杰斯特拉算法的分析过程一样
                    // 就是比较 如： A->C->B 和 A->B 哪一个较短
                    if (length < graph.getMatrix()[j][k]){
                        // 最短距离更新
                        graph.getMatrix()[j][k] = length;
                        // 中间顶点更新
                        graph.getVertexMatrix()[j][k] = i;
                    }
                }
            }
        }
    }
}

class FloydGraph{
    /**
     * 图中顶点的个数
     */
    private int vertexNum;

    /**
     * 图中的顶点
     */
    private char[] vertexArray;

    /**
     * 邻接矩阵
     */
    private int[][] matrix;

    private int[][] vertexMatrix;

    /**
     * 标记图中对应下标的顶点是否被访问过
     */
    private boolean[] isVisited;

    /**
     * unreachable 不可达
     * unreachable 定义为一个非常大的值
     * 表示两点之间不连通
     */
    private int unreachable = Integer.MAX_VALUE;

    public FloydGraph(int vertexNum, char[] vertexArray) {
        this.vertexNum = vertexNum;
        matrix = new int[vertexNum][vertexNum];
        vertexMatrix = new int[vertexNum][vertexNum];
        this.vertexArray = vertexArray;
        isVisited = new boolean[vertexNum];
        // 默认图中所有的点不可达
        for (int i = 0; i < vertexNum; i++) {
            for (int j = 0; j < vertexNum; j++) {
                if (i == j){
                    matrix[i][j] = 0;
                }else {
                    matrix[i][j] = unreachable;
                }
            }
        }
        // 对顶点关系矩阵做初始化
        for (int i = 0; i < vertexArray.length; i++) {
            Arrays.fill(vertexMatrix[i], i);
        }
    }

    /**
     * 为图填充数据，设置图中两点的距离
     * @param vertex1 顶点
     * @param vertex2 顶点
     * @param weight  两个连接的顶点间的权值（在这里就是两点间的距离）
     */
    public void setEdge(int vertex1, int vertex2, int weight){
        matrix[vertex1][vertex2] = weight;
    }

    public void showGraph(){
        for (int[] vertexLink : matrix){
            for (int vertex : vertexLink){
                System.out.printf("%-15d", vertex);
            }
            System.out.println();
        }
    }

    public void showVertexMatrix(){
        for (int i = 0; i < this.vertexNum; i++) {
            for (int j = 0; j < this.vertexNum; j++) {
                System.out.print(this.vertexArray[vertexMatrix[i][j]] + "  ");
            }
            System.out.println();
        }
    }

    public int getVertexNum() {
        return vertexNum;
    }

    public void setVertexNum(int vertexNum) {
        this.vertexNum = vertexNum;
    }

    public char[] getVertexArray() {
        return vertexArray;
    }

    public void setVertexArray(char[] vertexArray) {
        this.vertexArray = vertexArray;
    }

    public int[][] getMatrix() {
        return matrix;
    }

    public void setMatrix(int[][] matrix) {
        this.matrix = matrix;
    }

    public int[][] getVertexMatrix() {
        return vertexMatrix;
    }

    public void setVertexMatrix(int[][] vertexMatrix) {
        this.vertexMatrix = vertexMatrix;
    }

    public int getUnreachable() {
        return unreachable;
    }

    public void setUnreachable(int unreachable) {
        this.unreachable = unreachable;
    }

    public boolean[] getIsVisited() {
        return isVisited;
    }

    public void setIsVisited(boolean[] isVisited) {
        this.isVisited = isVisited;
    }
}
